package william.binarysearch;

/**
 * @author ZhangShenao
 * @date 2024/2/26
 * @description <a href="https://leetcode.cn/problems/search-in-rotated-sorted-array/description/">...</a>
 */
public class Leetcode33_搜索旋转排序数组 {
    /**
     * 采用二分查找思想
     * 因为有序数组只被旋转过一次,因此每次找到中点mid时,左、右两部分中一定有一部分是有序的
     * 首先找到有序的部分,判断target是否在有序部分的区间内,如果在,则再有序部分继续二分;否则在另一半的无序部分进行二分
     */
    public int search(int[] nums, int target) {
        //边界条件校验
        if (nums == null || nums.length == 0) {
            return -1;
        }

        int N = nums.length - 1;
        int l = 0;
        int r = N;
        while (l <= r) {
            int m = l + ((r - l) >> 1);
            if (nums[m] == target) {
                return m;
            }

            //因为有序数组只被旋转过一次,因此左、右两部分中一定有一部分是有序的,首先找到有序的部分
            if (nums[m] >= nums[0]) {    //左边有序
                if (target >= nums[0] && target < nums[m]) {  //找到满足条件的区间,继续二分
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            } else { //右边有序
                if (target > nums[m] && target <= nums[N]) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }

        }

        //未找到,返回-1
        return -1;
    }
}
